package a00_LeetCode.Stack;

import java.util.Stack;

/**
 * @Author quan
 * @Description 求栈中的最小值
 * 请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。
 * 执行push、pop和min操作的时间复杂度必须为O(1)。
 * @Date 2023/3/22 11:09
 */
public class Num0302_MinStack {
    public Num0302_MinStack() {

    }
    /**
     * 主要思想：一个栈无法同时获取栈中最小值和栈顶值，因此使用两个栈完成。
     * 第一个栈进行正常的入栈，可以获取栈顶值；第二个栈则只保存入栈过程中的最小值。
     */
    //创建两个栈
    Stack<Integer> s1 = new Stack<>();
    Stack<Integer> s2 = new Stack<>();
    //入栈
    public void push(int x) {
        s1.push(x);//s1正常入栈
        if(s2.isEmpty()){//如果s2是空的，当前值就是最小值直接入栈s2
            s2.push(x);
        }else{//此时s2中存在值
            int temp = s2.peek();//先获取s2中的栈顶值
            if(x > temp){//如果当前的值大于s2的栈顶值
                s2.push(getMin());//将s2中的最小值入栈到时
            }
            else{
                s2.push(x);//否则该值就是最小值入栈s2
            }
        }
    }
    //出栈
    public void pop() {
        s1.pop();
        s2.pop();
    }
    //在s1里面查看栈顶元素
    public int top() {
        return (int)s1.peek();
    }
    //在s2中获取最小值
    public int getMin() {
        return (int) s2.peek();
    }
}
